Encyclopedia of Graphics File Formats Companion

home *** CD-ROM | disk | FTP | other *** search

/ Encyclopedia of Graphics File Formats Companion / GFF_CD.ISO / software / mac / sparkle / spark202.hqx / Docs / Technical notes < prev

Wrap

Text File | 1994-05-17 | 28.7 KB | 583 lines

Contents: ABOUT MPEG ABOUT CONVERSION TO QUICKTIME ABOUT QT VM MISC SIZE AND TIMING NOTES ABOUT THE THREAD USAGE ABOUT THE RESOURCES. TIMING FOR WAITNEXTEVENT() AND FRIENDS ACCURATE TIMINGS FOR SPARKLE. This file contains various pieces of informationa about MPEG and Sparkle. Parts of it are notes I take for myself as I alter and test the program. I included them here because I thought some other mac programmers out there might be interested in such things. Read through what you care about and understand and ignore the rest. ------------------------------------------------------------------------------- ABOUT MPEG MPEG is an international standard for video compression. It compresses frames at two levels. Firstly frames are compressed internally, and secondly frame differences are compressed rather than transmitting full frames. To understand MPEG one should first understand JPEG. MPEG uses the same ideas as JPEG for much of its compression, and suffers from the same limitations. JPEG compression begins by changing an image's color space from RGB planes to YUV planes, where Y is the luminance (brightness of the image) and U and V store color information about the image. Half the color resolution in the horizontal and vertical planes is dropped, because the eye is less sensitive to color than to brightness. These YUV planes are then divided into 8 by 8 blocks of pixels. The 64 coefficients in this 8 by 8 block are fourier transformed concentrating the energy of the image in a few coefficients at low frequencies. The high frequency terms of the fourier transform can be discarded as the eye is not sensitive to them. The resultant fourier transform coefficients are then encoded using a variable length coding scheme (basically Huffman coding) so that frequently occuring patterns of coefficients are transmitted in few bits and rare patterns transmitted in many bits. MPEG goes beyond this by adding support for inter-frame compression. This compression works by realizing that most video consists of foreground objects moving over a largely static background. Thus rather than transmit the foreground and background pictures over and over again, what is transmitted is the motion of the foreground objects. Note that this is different from the way QuickTime does interframe compression. What QuickTime does is just to subtract the two images from each other and compress the resultant image (which is hopefully largely blank space.) The MPEG scheme gives much better compression, but is much harder to program. It is essentially a pattern recognition problem, looking at a set of frames and deciding what pixels in the frame correspond to moving objects---the sort of thing humans are very good at and computers very bad at. For this reason, a complete MPEG compressor is complex and very slow. MPEG movies consist of three types of frames. I-frames are like JPEG images and are compressed by themselves. P-frames are compressed based on motion relative to a previous frame. B-frames are compressed based on motion relative to both a previous frame AND a future frame. How do you know what the future frame is? Well the MPEG data is not stored in the same order as it is displayed. You have to decode future frames before the B-frames on which they depend, then buffer the future frame somewhere. This is why MPEG players need rather more memory than QuickTime players. As an example, here's a comment from my code. //About these three counters: //DecodedFrameNumber tells where we are in the file which we are currently //parsing, and is needed to find one's way around this file. It is incremented //every time a new frame is parsed. //DisplayedFrameNumber gives the number in temporal sequence of the frame that //is currently being shown on the screen. //For I and P MPEGs these are the same, but not for B MPEGs. For example a //B MPEG may have the sequence: // 0 1 2 3 4 5 6 7 8 9 10 decodedFrameNumber // I P B B I B B P B B I frameType // 0 3 1 2 ! 2 0 1 5 3 4 ! 2 display number (within group) // --------------|-----------------------|---- group boundaries // 1 4 2 3 7 5 6 10 8 9 ? displayedFrameNumber //Note how the frames are clustered in groups, within which the Pict structure's //temporalReference field give the display number within that group. //The displayedFrameNumber is basically a sum of these as one passes from group //to group, along with a condition of starting at one, rather than zero. //Now consider random access: //If we want to make a random access jump to a frame around displayed frame 5, //we will be vectored to decodedFrameNumber 4, which will then be decoded, //skipping past decodedFrameNumbers 5 and 6 (which depend on another frame in //addition to decodedFrameNumber 4, and hence can't be displayed) to finally //arrive at displaying decodedFrameNumber 4 as displayedFrameNumber 7. //the variable decodedFrameNumberOfVisibleFrame keeps track of this fact that //the displayedFrameNumber 7 actually represents decodedFrameNumber 4. //This information is necessary when stepping backwards through an MPEG. //If we are at displayedFrameNumber 7 and step back, we will look back for I-frames //until we get to the I-frame at decodedFrameNumber==4. But this is the I-frame of //the image we are just displaying, so we actually need to then step back to an //earlier I-frame. //This complication is all necessary partially because of the way MPEG forward //coding works, with the frame sequence on file not corresponding to the viewed //sequence, also partially because some B MPEGs do not have valid data for //their Pict.temporalReference fields, thus one cannot rely on that field to be //valid but one has to maintain a state machine as one parses through the file. An MPEG movie can consist of only I-frames. This will be far from optimally compressed, but is much easier to encode because the pattern recognition is not needed. Such a movie is pretty much what you would get if you made a QuickTime movie and used the JPEG codec as the compression option. Because the I-frame movie is so much easier to calculate, it is much more common. Sparkle checks if a movie uses only I-frames and if so reduces its memory requirements since such movies do not need complex buffering. In the PC world, many people talk about XING type MPEGs which are pure I-frame MPEGs. These are produced by XING hardware on PCs and played back using the XING MPEG player. One problem with the MPEG standard is that many vendors seem to feel which parts of it they support are optional. XING, for example, often does not ends its MPEGs properly. It does not start frame numbering properly, and does not correct frame numbering after MPEGs are edited. GC technologies produces MPEGs that have the frames essentially random numbered, and has garbage frames at the start of its MPEGs. Wherever possible I have tried to adapt my code to common pathologies in MPEG encoders. I have also built in powerful yet computationally cheap error-detection and recovery. For example a recent MPEG posted to usenet drew widespread complaints because some of the uuencoded text was garbled and the resultant MPEG crashed pretty much every decoder out there. But Sparkle noticed the error and went on quite happily. Sparkle has also proved quite robust in the face of MPEGs I have deliberately corrupted. If you come across any MPEG file that causes Sparkle to crash or produce garbage, I WANT TO KNOW ABOUT IT. With a copy of the file, I can trace through Sparkle, find just what causes the crash, and make Sparkle even more robust. For more details on MPEG, read the MPEG FAQ on USENET. It is posted once a week to the picture groups and to news.answers. ------------------------------------------------------------------------------ ABOUT CONVERSION TO QUICKTIME The following are notes I've made on conversion to QuickTime. I have investigated this issue extensively, but not exhaustively. If someone has comments on the subject---more extensive notes than I have, corrections, whatever, please tell me. All times I give are on my SE/30 with a 32-bit screen. People should extrapolate to their machines---I guess LC IIs are about half as fast and Centris/Quadras three to six times as fast. The useful codecs are video, cinepak (used to be compact video) and jpeg. JPEG compression at normal quality gives files of very good quality and not much larger than pure I-frame MPEGs. A 120x160 image can play back at about 4fps. Translated to an 040 and you get a useful frame rate. However JPEG has a major problem in that when it decodes to a 32bit screen, it draws directly to the screen, not to an offscreen Gworld unlike other codecs. This produces movies with obvious tearing artifacts. When fast-dithering is used to draw to other screen depths, it works fine. I don't understand why this problem with 32 bit screens should be the case, but I have told Apple about this problem and maybe it'll be fixed in a later release of QuickTime. Meanwhile write to Apple and complain---they are holding back a useful capability. With the video and cinepak compressors, it is very important to check the key-frame rate checkbox. Key-frames are like MPEG I-frames. They are compresed standalone and do not depend on other frames. The other frames produced by the movie codecs depend on previous frames. Setting the key-frame rate guarantees that at least that rate of key-frames (one frame in used. for example) will be used. Checking the key-frame rate checkbox allows the movie to use intra-frame compression (ie not just key-frames) and gives movies half as small as they would otherwise be. The lower you set the key frame rate to (this means a larger number in the QuickTime saving options dialog box) , the smaller you movie will be. For example a 72K MPEG (48 frames, 120x160, pure I-frame) became a 290K movie without keyframes, a 160K movie with a key-frame rate of 1 in 8, and a 138K movie with a key-frame rate of 1 in 96. The price you pay for a low key-frame rate is that the movie has more difficulty when playing backwards, or when randomly jumping around. I don't find it a problem and usually use a key-frame rate of about 1 in 100, but try for yourself to see what things are like. Video gives better quality results when a higher key-frame rate is used. Strangely cinepak appeared to give lower quality results (as well as a larger movie) when more key-frame were used. I'll have to investigate this further---I may have become confused when I was making the measurements. Anyone want to confirm or deny this? (For comparison, this same movie became a 90K JPEG movie.) I find video and cinepak give much the same file sizes at the same (around normal) quality setting. The cinepak file is consistently a little larger, but not enough to matter. The video file is consistently lower quality for the same size as the cinepak file. However the video low quality artifacts (blocks of solid color) I find less psychologically irritating that the cinpeak low quality artifacts (general fuzzing of borders like everything is drawn in crayon and watercolor). However cinepak has the advantage of playing back much faster than video. For a 120x160 image on my 32bit screen, I can get smooth playback with cinepak at 24fps. Video can do smooth playback up to about 16 fps. Fast dithering seems to be a good job for speed (at the cost of quality). Unlike earlier versions of QuickTime, with 1.6.1 I found the same speed of playback (ie same degree of skipping frames or not) at every screen depth but 2 bit depth. Cinepak can support a largish MPEG to QuickTime movie (352x240) at 6fps on my mac, but no faster. Compression using cinepak is SLOW SLOW SLOW. A 120x160 frame takes about 10 seconds to compress. A 352x240 frame takes about a minute. In this time your mac is stuck---it looks like it has crashed. Don't start saving to cinepak QuickTime unless you are prepared to walk away from your mac and not touch it until it's done. QuickTime 1.5 did not include anyway to do this compression in small chunks so that it would run nicely in the background. I received word today that QuickTime 1.6 does have this capability, so once I get the relevant techincal documents and read them, I will add this ability. See the WHY DOESN"T SPARKLE DO... section for more information about MPEG frame rates and their relationship to QuickTime frame rates. ------------------------------------------------------------------------------ ABOUT QT VM Recently an INIT called QT VM has been released. This attempts to speed up the behavior of QuickTime under virtual memory. What it does is that when an application makes a NewGWorld call, asking that the GWorld be placed in TempMem, the call fails. The idea is that it is faster to force the memory manager to move memory around the app's partition, purging and consolidating, than it is to allocate the GWorld in new memory which may force paging to disk. For many situations this is true, but not for Sparkle. Sparkle tries to make itself use smaller partitions by creating GWorlds in TempMem. With the QT VM INIT enabled, it can't do that and has to create the GWorlds in its partition. This means that the partition size has to be made larger occasionally. ================================================================================ MISC SIZE AND TIMING NOTES These are rough notes I take as I alter the code, partially out of interest and partially to guide me in where I need to change things. They may be of interest to some of you. They are now timed on my new Q610 and the SE/30 is in the hands of my little brother. Like the SE/30 timings given above, they may not be be consistent with each other as they reflect the state of the code at different times. In between I may change the code quite a bit---mainly of interest are the differences within any group of results. Timings for Erika1.MPG under Sparkle 2.0 on my Q610. This is a 41 frame pure I 120x160 frame MPEG. These times are for a version of the code that does not call WNE while playing: 1) Effect of the screen depth/dithering on times: (non-optimized code) 24-bit color: 8.2 s 16-bit color 9.2 s 8-bit color 10.1 s 8-bit grey 8.6 s Conclusion: probably worth adding hints to speed up some parts of the code to compensate for the dithering times: 1) For 8 bit color use 4x4 IDCT. 2) For 8 bit grey, omit YUV->RGB conversion. 3) For 16 bit color, use a special YUV->RGB conversion. 2) Effect of various TC6 optmizations: (24-bit screen) Defer and combine stack adjusts: 7.8 s Suppress redundant loads: 7.7 s Automatic register assignment: 7.6 s Global: Induction variables: 7.4 s Common sub-expression elimination: 7.3 s Code motion: 7.2 s Register coloring: 6.6 s 3) Effects of various displayings: (no optimizations) No progress proc at all (implies NOTHING ever updated on screen): 6.7 s Progress proc called but does nothing: 6.8 s Progress proc updates movie controller/text track only: 7.6 s Progress proc updates only MPEG frames, not movie controller 7.3 s Progress proc updates both: 8.1 s Conclusion: of the 8.1 s, 0.8 s=10% is used updating movie controller and 0.5 s= 6% is used updating the MPEG frames. 4) Effect of the time allowed a thread before it yields: Yield time=6000 ticks (ie never yield) 8.0 s 180 ticks 8.1 s 60 ticks 8.2 s 20 ticks 8.6 s One would rather have a 20 tick time than a 60 tick time for increased user interactivity, but the time cost is rather stiff. However by implementing a new thread scheduler, I should be able to reduce this cost somewhat. 5) Effect of yield time in the background: We convert Erika1.MooV to an I-frame MPG. FG time (yield time of 30 ticks): 1min 12s BG time (yield time of 10 ticks) 2min 30s BG time (yield time of 30 ticks) 2min 04s Conclusion: The longer yield time is obviously better but makes things more choppy. Best is probably to implement a timer keeping track of how fast we are getting background NULLs and increasing bgYieldTicks as we notice less fg activity. 6) Note: I have tried to put yield brackets around all the hotpoints of the code to make it run well in background. The main problem for now, that I need to work around (ProgressProcs ?) is when the new frame is requested for coding an MPEG or QT movie from a QT document. The fiddling that goes on to obtain this frame can be fairly substantial, taking as long as 70 or 80 ticks for a simple 160x120 movie. My guess is that QT doesn't do very smart caching about non-synch frames and has to decompress a long sequence to get to these frames. Anyways, because of this we're stuck with a basic jerkiness at that granularity for now. 7) Effects of four different P algorithms. We convert Erika1.MooV to four MPEGs, all using a PPPI pattern, with an I-quantization of 8 and a P-quantization of 10. Algorithm: Time: Size: Logarithmic 1:45 min 53 953 Two level 2:45 min 54 328 Subsample 3:45 min 54 765 Exhaustive 5:55 min 54 677 There was no obvious difference in quality between these MPEGs (and they were all pretty lousy). Thus there seems no real advantage to using anything but the fastest algorithm. 8) Effects of P-quantization. Evene with a P-quantization of 8, the above setup does not produce as good an image as a pure I sequence (although the file size of 62K is much smaller.) This appears to be largely due to the successive dependencies caused by the three successive P frames. Is it better to reduce the number of Ps or lower the P-quantization? Using same pattern but P-quantization of 4 gives a file size of 98K and a quality lower than the pure I-frames (though certainly better than what we had). Using a pattern of PPI and P-quantization of 8 gives a file size of 71K and the same sort of quality. Using a PBBIBB pattern and all quantizations as 8 gives a size of 60K and the same sort of quality. Conclusions: 1) I need to use a higher quality source of images to investigate these affects. 2) I think the P and B pattern matching criteria may be a bit dodgy, or maybe some part of my code has problems with half-pixels or such. 9) Effect of buffer size. I played a 750K MPEG of 150 frames. With a buffer size of two frames, it took 36s. With a buffer size of 200 frames (ie entire movie) it took 33s. Thus the larger buffer buys about 10% speed. So maybe, when time, create massive buffers which are in some way shrinkable. ---------------------------------------------------------------------------------- Sizings for Erika1.MPG under Sparkle 2.0 1) Using only I-frame encoding with varying I-quantization: I-quantization size in bytes 1 237 307 2 179 960 4 132 916 8 92 210 16 66 821 24 42 658 //These two values are bogus, now that I've cleaned up the MPEG generating //code. // 32 37 094 // 64 25 955 DC terms only 21 695 Notes: Ñ These sizes are probably slightly larger than necessary as at present I do not pad the excess pixels where frame size is smaller than the frame size in macroblocks, thus the DCT is encoding crud at those borders. By padding those to DC we'll get a small shrinkage in size. ! This was fixed in version 2.01. The shrinkage was way more than I expected, of the order of 15%. Ñ With this set of images (which were pretty lousy to begin with) a quantization level of 8 produced acceptable images, while a level of 16 produced unnacceptable quality. ================================================================================ ABOUT THE THREAD USAGE I have nothing special to say about using threads except that I recommend all serious Mac coders read the Apple documentation and use them. They make life so much easier. The 1.x code was full of the most ghastly and convoluted logic to enable breaking out of the MPEG decoder into the main event loop and back again. However the 2.x code for encoding is ridiculously simple. We simply have the encoder, written (like a UNIX process or such) as on long loop, then in the loop at appropriate points we make Yield() calls. The one thing that one has to be careful of is using exception handling in the TCL. Because this is based on application wide globals, dreadful things can happen in your thread when an exception occurs, a string of CATCH handlers is followed up the stack, and at some point you leave the stack of the thread and enter the "stack of the application". My solution to this was to use custom thread context switchers which, on every context switch, swap the appropriate exception handling globals. The custom context switchers also become a good place for updating the timings of each thread and setting when it will next yield. Another good idea is to encapsulate the thread in an object, then call that object to yield instead of calling a Thread Manager yield directly. The advantage of this is that the thread object can then see if the thread manager is installed ---if so it yields, ---if not it can test for command-. and abort, or simly return control. This makes the code inside each inner loop (MPEG encoding or decoding or QT encoding) much cleaner---simply yields with no tests for this or that special situation. At present I'm only using cooperative threads. It's not clear to me that switching to pre-emptive threads is a useful excercise. One problem is, of course, that pre-emptive threads make life rather trickier and coding more complex. More to the point, pre-emptive threads only get half the CPU time, while the WaitNextEvent() loop gets the other half. So by switching to them I'd get lose half my speed, and not gain much. I might gain slightly smoother user event support, especially in the background, but that's not that bad right now and will improve when I install a custom thread scheduler in place of the hokey quick kludge I'm using right now. If anyone out there has worked with pre-emptive threads and has opinions on them one way or the other, please let me know. A second major change in the 2.x code is I have now structured things around a model of video source objects and video encoder objects, with any video source able to be linked to any video encoder. This makes for very orthogonal extensible code. The natural extension of this is now to define more video sources. In particular as soon as I can I hope to get to work on morphing routines, with output that can be played to screen or saved in whatever video formats I'm supporting by that stage. I have some ideas for morphing algorithms, but if anyone can send me code, or tell me whence I can ftp it (yes this usage of whence is correct) I'll obviously be able to get going faster. Along the same lines, anyone know where I can get AVI source, or the AVI specs so I can add AVI support? UPDATE FOR 2.1 The connection between threads is now based on a message queue associated with each thread. When a message is passed to a thread it is enqueued. If a thread is busy (ie playing or saving to some format) and asks for messages when there are none it is given a NULL message which it uses to perform idle processing, otherwise it is put to sleep. Obviously this mechanism looks very like the Process Manager's behavior. Two consequences emerge from this. The first is that I can now, in the main event loop, peek for events and if there are no events in my main event queue, return immediately. This allows me to avoid the overhead of (very expensive) main event loop while maintaining high interactivity. The cost of high interactivity is thus reduced from about 12% of play time to about 1%. The second is that it makes it much easier to glue the user interface to a different MPEG encoder or decoder (eg dedicated hardware) because the connection between the user interface and the threads doing the work is asynchronous. ================================================================================ ABOUT THE RESOURCES. The default for the flags for all resources is purgable. However there are some exceptions. Ñ╩DLOGs and DITLs that will be opened by the TCL needed to be set nonpurgable because of a bug in the TCL. I have altered CDLOGDialog to fix this and these resources can now be purgable. Ñ The DLOGs and DITLs used by CustomGetFile() and CustomPutFile() appear to need to be non-purgable even though IM says they can be purgable. If they are set purgable the MemHell INIT registers errors during CustomGetFile() and CustomPutFile(). Ñ╩Menus may not be purgable because the menu manager does not allow that. Given this, one might as well make them preload and locked. Likewise for the MBAR. Ñ╩The DaTa resources, used to construct decoding tables, are mostly preload locked and treated just liked const global data. However there are a few small tables for which it is advantageous to load these into genuine global arrays. For that case, the resources are marked purgable. Ñ Marking resources Protected does not ever seem to be useful. Ñ If a dialog/alert makes uses of an ictb to change the font of text items, the associated dctb or actb must also be present or else nothing will happen. Ñ╩Note that some of the dctb/itcb resources may appear redundant. However they prove to be necessary in unexpected ways. For example if they are not present for the CustomPutFile() DLOG, the dialog box drawn on screen will use dotted grey pattern to draw the items in the scrolling list of files, rather than using a nice grey color. ================================================================================ TIMING FOR WAITNEXTEVENT() AND FRIENDS I wrote a simple loop that timed 200 passes each of these calls, and recorded the times. For my outer loop over events, I want to know the cheapest way of ascertaining whether I should get an event or not: For the last item, we timed 200 loops over the TCL core event routine, CApplication::Process1Event(), with nothing happening. Time (in ticks) for 200 passes of: EventAvail() 30 GetNextEvent 62 WaitNextEvent0 93 (WNE with mouseRegion==NULL and sleep==0) WaitNextEvent1 493 (WNE with mouseRegion==NULL and sleep==1) Loops over TCL Idle 1027 ================================================================================ ACCURATE TIMINGS FOR SPARKLE. These are timings taken for Sparkle 2.1 on my Q610 with 24bit color. The idea was to accurately time what were the hot spots in MPEG playback. All times reported are in ticks (60th of a second) and reflect the second time the operation was performed. Very consistently it was found that the first time an operation was performed took 11 ticks longer than subsequent times, presumably reflecting loading in purgable resources and such initialization. Times to play Erika1.mpg. All times reflect playback time for 40 frames. The first time is split into times with debugger and without. Once the program never calls WNE the debugger time becomes the same as the app time. Standard parameters, thread time quantum=20 ticks, delay before yielding to other apps via WNE was infinity When debugging time was 433 ticks 5.5 fps As an application 402 ticks 6.0 fps If we set an infinite yield time 399 ticks 6.0 fps // All subsequent times use an infinite yield time. If we don't use a progress proc 370 ticks If we use a progress proc but it doesn't update the screen 373 ticks If we update the screen but don't use a movieController 332 ticks //All subsequent times use an infinite yield time and no movie controller. If we omit YUV to RGB conversion 225 ticks If we use only a DC term IDCT 229 ticks If we don't even call IDCT 226 ticks If we don't call ReconstructIBlock() 295 ticks If we use a 4x4 pseudo IDCT (very rough---can be written to be faster) 320 ticks If we use QUALITY_STANDARD not QUALITY_HIGH 324 ticks If we use QUALITY_LOW not QUALITY_HIGH 294 ticks From this we conclude that for 40 frames: WNE/thread yield overhead=3 to 4 ticks in an app, but about 35 ticks when debugging. (This is nice---it means my scheme for drastically cutting WNE time works!) Progress proc function call overhead= 3 ticks. CopyBits to 24bit screen= 25 ticks MovieController overhead= 40 ticks YUV to RGB =105 ticks IDCT =100 ticks Reconstruct I blocks = 30 ticks (does cropping of the results) So Huffman = 95 ticks From these results we can expect to shave 15 ticks off the IDCT by using 4x4. We can shave off 30 ticks by using QUALITY_LOW. We can probably cut YUV to RGB in two or more by using the upper 5 bits of each of YUV into a table. Some further results are: Suppose we simply run the movie controller/text track and don't ever call the MPEG code. This takes about 55 ticks. Suppose we hide the movie controller: 422 ticks (cf 433 ticks) text track : 418 ticks both : 408 ticks